Focusing on large-scale vehicle routing problem with heterogeneous fleet, a new neighborhood mapping method, namely density clustering based removal heuristic algorithm, was proposed under the Adaptive Large Neighborhood Search (ALNS) frame work. ALNS includes two phases:destruction and reconstruction, which provides optimized solution by destroying and reconstructing current solution. In the destruction phase, a routine was randomly selected to get clusters by density clustering, and then the stores were removed from the routine according to the clusters. In reconstruction, Greedy or Regret-2 insert algorithm was randomly chosen to place those removed stores into proper routine. Test results on benchmark instances validate the effectiveness of the proposed method. Compared with other existing algorithms, the ALNS density clustering based removal heuristic algorithm has lower rate of error and better quality of solutions; in real situations, the proposed algorithm can provide optimized solution in limited time.